package cn.fxzhang.leetcode.no03;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;

/**
 * 368. 最大整除子集
 *
 * 类型：枚举/数值
 * 题解：排序后从大到小枚举，先找出比当前数小且能整除的，再找比当前数大的
 * 时间复杂度：O(N^2)
 * 空间复杂度：O(N)
 *
 * 提交记录(1/1)：
 * 执行用时: 41 ms, 击败了10.94%
 * 内存消耗: 38.3 MB, 击败了98.15%
 * todo 正确性待验证
 * @author 张晓帆
 * @date 2021/4/23
 */
public class P0368_Largest_Divisible_Subset {

    public List<Integer> largestDivisibleSubset(int[] nums) {
        int n = nums.length;
        Arrays.sort(nums);
        List<Integer> ans = new ArrayList<>();
        int max = 0;
        // 从大到小枚举
        for (int i=n-1; i>=0; i--){
            int num = nums[i];
            List<Integer> list = new ArrayList<>();
            list.add(num);
            // 依次将nums[i]%nums[j]=0的数加入集合
            for (int j=i-1; j>=0; j--){
                if (num%nums[j] == 0){
                    list.add(nums[j]);
                    num = nums[j];
                }
            }
            // 依次将nums[j]%nums[i]=0的数加入集合
            num = nums[i];
            for (int j=i+1; j<n; j++){
                if (nums[j]%num == 0){
                    list.add(nums[j]);
                    num = nums[j];
                }
            }
            if (list.size() >= max){
                max = list.size();
                ans = list;
            }
        }
        Collections.sort(ans);
        return ans;
    }

}
